package com.zyk.java8;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/23 17:25
 */
public class MatrixPre {

    // 二维数组前缀和
    public static int[][] preMatrix(int[][] matrix) {
        // sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1]
        int R = matrix.length, C = matrix[0].length;
        int[][] sum = new int[R][C];
        sum[0][0] = matrix[0][0];
        // 第一行
        for (int c = 1; c < C; c++) {
            sum[0][c] = sum[0][c - 1] + matrix[0][c];
        }
        // 第一列
        for (int r = 1; r < R; r++) {
            sum[r][0] = sum[r - 1][0] + matrix[r][0];
        }
        // 从左往右, 从上往下
        for (int r = 1; r < R; r++) {
            for (int c = 1; c < C; c++) {
                sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1] + matrix[r][c];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8}
        };
        int[][] sum = preMatrix(matrix);
        for (int[] nums : sum) {
            System.out.println(Arrays.toString(nums));
        }
    }

}
